package day12;

import java.util.Arrays;
import java.util.Scanner;

public class demo6 {

        public static void main(String[] args) {
            Scanner in=new Scanner(System.in);
            int n=in.nextInt();
            int V=in.nextInt();
            int []w=new int[n+1];
            int []v=new int[n+1];
            for(int i=1;i<=n;i++){
                v[i]=in.nextInt();
                w[i]=in.nextInt();
            }
            int[]dp=new int[V+1];
// Arrays.fill(dp,0);
            for(int i=1;i<=n;i++){
                for(int j=V;j>=v[i];j--){
                    dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
                }
            }
            System.out.println(dp[V]);

            Arrays.fill(dp,0);


            for(int i=1;i<=V;i++){
                dp[i]=-1;
            }

            for(int i=1;i<=n;i++){
                for(int j=V;j>=v[i];j--){
                    if(dp[j-v[i]]!=-1){
                        dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
                    }
                }
            }
            System.out.println(dp[V]==-1?0:dp[V]);
        }

}
